package com.company.string;

/**
 * @author jrue
 * @version 1.0
 * @date 2020/1/29 20:46
 */
public class Kmp {

    private int[] next(String s) {
        int[] next = new int[s.length()];
        int k = -1;
        int j = 0;
        next[0] = -1;
        while (j < s.length() - 1) {
            if (k == -1 || s.charAt(k) == s.charAt(j)) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }

        return next;
    }

    public int kmp(String s1,String s2) {
        int[] next = next(s2);
        int i = 0,j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (j == -1 || s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        return i - j;
    }

    public static void main(String[] args) {
        String s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaabcaaa";
        String s = "aabc";
        long time01 = System.currentTimeMillis();
        System.out.println(new Kmp().kmp(s1, s));
        long time02 = System.currentTimeMillis();
        System.out.println(time02 - time01);
        System.out.println(s1.indexOf(s));
        long time03 = System.currentTimeMillis();
        System.out.println(time03 - time02);
    }
}
